In this paper we present a novel probabilistic sampling-based motion planningalgorithm called the Fast Marching Tree algorithm (FMT*). The algorithm isspecifically aimed at solving complex motion planning problems inhigh-dimensional configuration spaces. This algorithm is proven to beasymptotically optimal and is shown to converge to an optimal solution fasterthan its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT*algorithm performs a "lazy" dynamic programming recursion on a predeterminednumber of probabilistically-drawn samples to grow a tree of paths, which movessteadily outward in cost-to-arrive space. As a departure from previous analysisapproaches that are based on the notion of almost sure convergence, the FMT*algorithm is analyzed under the notion of convergence in probability: the extramathematical flexibility of this approach allows for convergence ratebounds--the first in the field of optimal sampling-based motion planning.Specifically, for a certain selection of tuning parameters and configurationspaces, we obtain a convergence rate bound of order $O(n^{-1/d+\rho})$, where$n$ is the number of sampled points, $d$ is the dimension of the configurationspace, and $\rho$ is an arbitrarily small constant. We go on to demonstrateasymptotic optimality for a number of variations on FMT*, namely when theconfiguration space is sampled non-uniformly, when the cost is not arc length,and when connections are made based on the number of nearest neighbors insteadof a fixed connection radius. Numerical experiments over a range of dimensionsand obstacle configurations confirm our theoretical and heuristic arguments byshowing that FMT*, for a given execution time, returns substantially bettersolutions than either PRM* or RRT*, especially in high-dimensionalconfiguration spaces and in scenarios where collision-checking is expensive.
展开▼
机译：在本文中，我们提出了一种新颖的基于概率采样的运动规划算法，称为快速行进树算法（FMT *）。该算法专门针对解决高维配置空间中的复杂运动计划问题。该算法被证明是渐近最优的，并且被证明比最先进的算法（主要是PRM *和RRT *）收敛到最优解。 FMT *算法对预定数量的概率绘制样本执行“惰性”动态编程递归，以生长路径树，该路径树在到达成本空间中稳定地向外移动。与以前的基于几乎肯定收敛的分析方法不同，FMT *算法是在概率收敛概念下进行分析的：这种方法的数学外灵活性允许收敛速率边界，这是最优领域中的第一个方法。基于采样的运动计划。具体来说，对于调整参数和配置空间的特定选择，我们获得了阶次$ O（n ^ {-1 / d + \ rho}）$的收敛速率边界，其中$ n $是采样点，$ d $是配置空间的维数，$ \ rho $是任意小的常数。我们继续证明FMT *上许多变体的渐近最优性，即当配置空间采样不均匀，成本不是弧长时，以及基于最近邻居的数目而不是固定的连接半径进行连接时。一系列尺寸和障碍物配置的数值实验通过证明FMT *在给定的执行时间上比PRM *或RRT *返回的解决方案要好得多，从而证实了我们的理论和启发式论点，尤其是在高尺寸配置空间以及碰撞检查的情况下价格昂贵。
展开▼
